public class Solution {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


    private TreeNode prev = null;
    private TreeNode head = null;

    private void inOrderConvert(TreeNode node) {
        if (node == null) return;

        // 递归遍历左子树
        inOrderConvert(node.left);

        // 处理当前节点
        if (prev == null) {
            head = node; // 当前节点是最左边的节点，即双向链表的头节点
        } else {
            prev.right = node; // 将前一个节点的右指针指向当前节点
            node.left = prev; // 将当前节点的左指针指向前一个节点
        }
        prev = node; // 更新前一个节点为当前节点

        // 递归遍历右子树
        inOrderConvert(node.right);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        inOrderConvert(pRootOfTree);
        return head;
    }
}
